

function say() {
    alert("99. 恢复二叉搜索树");
}
say();


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function (root) {
    //9:28-45
    // 转化问题 BST->有序数组
    var arr = []
    dfs(root, arr)
    // console.log('sz', arr) // sz [ 3, 2, 1 ] // sz [ 1, 3, 2, 4 ]
    //求数组中的逆序 已知数组中两个元素逆序了,交换后就正常了,求这两个元素; 排序,完了不同的就是目标元素

    var sortArr = arr.slice()
    bubleSort(sortArr)
    var idx = 0
    for (var i = 0; i < sortArr.length; i++) {
        if (sortArr[i] != arr[i]) {
            idx = i
            break
        }
    }

    changeDfs(root, sortArr[i], arr[i])
};

function changeDfs(root, p, q) {
    if (root) {
        if (root.val == p) {
            root.val = q
        } else if (root.val == q) {
            root.val = p
        }
        changeDfs(root.left, p, q)
        changeDfs(root.right, p, q)
    }
}

function bubleSort(arr) {
    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

function dfs(root, arr) {
    if (root) {
        dfs(root.left, arr)
        arr.push(root.val)
        dfs(root.right, arr)
    }
}
